perm filename REV.10[CRE,BGB] blob
sn#101492 filedate 1974-05-09 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 WORD BIT REVERSAL
C00004 00003 The Gosper triple tricky is merely the observation that
C00006 00004 BYTE SERIAL SCHEMES
C00007 00005 TITLE D1
C00008 ENDMK
C⊗;
WORD BIT REVERSAL
Baumgart
ABSTRACT: Thirty or so PDP-10 programs for reversing the order
of the bits in a word are presented and anaylsed; although these
programs were written for their peculiar entertainment value, they
are subsequently discussed with respect to proving their correctness
and equivalence and with respect to generating
arbitrary repacking programs automatically.
A series - Simple Serial.
B series - Gosper Triple Tricky.
C series - Byte Serial.
D series - Nested Byte Swapping.
E series - Schroeppel Bit-Rev'ing.
F series - Combination Schee
TITLE A1
INTERN REV ; 183 memory cycles.
A←←1 ; 8 words long.
B←←2
CNT←←3
P←←17
REV: MOVEI CNT,=36 ;1
L: LSHC 1 ;36
EXCH A,B ;36
LSHC -1 ;36
EXCH A,B ;36
SOJG CNT,L ;36
MOVE A,B ;1
POPJ P, ;1
END
TITLE A2
INTERN REV ; 57 memory cycles.
A←←1 ; 7 words.
B←←2
PTR←←3
P←←17
REV: MOVE PTR,[POINT 1,B,-1] ;1
L: IDPB A,PTR ;18 average
LSH A,-1 ;18 average
JUMPN A,L ;18 average
MOVE A,B
POPJ P,
END
The Gosper triple tricky is merely the observation that
TRCE PAIR
TRCE PAIR
TRCE PAIR
will swap two bits in the right half of the ac; where PAIR is a
suitable mask indicating the two bit position you wish to swap.
One might hope that this code fragment could be the basis of
a good REV program.
TITLE B1 TRIPLE TRICKY with COMPUTED MASK.
INTERN REV ; 156 memory cycles.
A←←1 ; 12 words long.
P←←17
LBIT←2
RBIT←3
MASK←4
REV: MOVEI RBIT,1 ; 1
HRLZI LBIT,400000 ; 1
L: MOVE MASK,LBIT ;18
IOR MASK,RBIT ;18
TDCE A,MASK ;18
TDCE A,MASK ;13.5
TDCE A,MASK ;13.5
LSH LBIT,-1 ;18
CAMN LBIT,RBIT ;18
POPJ P, ; 1
LSH RBIT,1 ;18
JRST L ;18
END
TITLE B2 TRIPLE TRICKY with TABLE MASK.
INTERN REV ;101 memory cycles.
A←←1 ; 25 words long.
CNT←←2
MASK←←3
REV: MOVEI CNT,=18 ; 1
L: MOVE MASK,TABLE(CNT) ;18
TDCE A,MASK ;18
TDCE A,MASK ;13.5
TDCE A,MASK ;13.5
SOJG CNT,L ;18
POPJ P, ; 1
TABLE: FOR I←0,=17{
((1B0)⊗(-I))∨(1⊗I)}
END
BYTE SERIAL SCHEMES
TITLE C1 NAIVE STRAIGHT TABLE LOOKUP IN THREE 12-BIT BYTES.
INTERN REV
A←←1
B←←2
X←←3
P←←17
REV: LDB X,[POINT 12,A,11]
MOVE X,TABLE(X)
DPB X,[POINT 12,A,35]
LDB X,[POINT 12,A,23]
MOVE X,TABLE(X)
DPB X,[POINT 12,B,23]
LDB X,[POINT 12,A,35]
MOVE X,TABLE(X)
DPB X,[POINT 12,B,11]
MOVE A,B
POPJ P,
END
TITLE C2
INTERN REV ;34 memory cycles.
A←←1 ;72 words long.
AA←←2
BB←←3
CNT←←4
PTR←←5
P←←17
REV: MOVE PTR,[POINT 6,A,-1] ;1
MOVEI CNT,6 ;1
L: ILDB AA,PTR ;6
MOVE AA,TABLE(AA) ;6
LSHC AA,-6 ;6
SOJG CNT,L ;6
MOVE A,BB ;1
POPJ P, ;1
END
TITLE D1
INTERN REV ;27 memory cycles.
A←←1 ;25 words long.
B←←2
C←←3
REV: MOVS A
ROTC 9
HRL A,
MOVE C,A
AND C,[007007007007]
LSH C,6
MOVE B,A
AND B,[070070070070]
IOR C,B
LSH A,-6
AND A,[007007007007]
IORB A,C
AND C,[111111111111]
LSH C,2
MOVE B,A
AND B,[222222222222]
IOR C,B
LSH A,-2
AND A,[111111111111]
IOR A,C
POPJ P,
END